{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Word Subsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: wordSubsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #单词子集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个字符串数组 <code>words1</code>&nbsp;和&nbsp;<code>words2</code>。</p>\n",
    "\n",
    "<p>现在，如果&nbsp;<code>b</code> 中的每个字母都出现在 <code>a</code> 中，<strong>包括重复出现的字母</strong>，那么称字符串 <code>b</code> 是字符串 <code>a</code> 的 <strong>子集</strong> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>\"wrr\"</code> 是 <code>\"warrior\"</code> 的子集，但不是 <code>\"world\"</code> 的子集。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果对 <code>words2</code> 中的每一个单词&nbsp;<code>b</code>，<code>b</code> 都是 <code>a</code> 的子集，那么我们称&nbsp;<code>words1</code> 中的单词 <code>a</code> 是<em> </em><strong>通用单词</strong><em> </em>。</p>\n",
    "\n",
    "<p>以数组形式返回&nbsp;<code>words1</code> 中所有的通用单词。你可以按 <strong>任意顺序</strong> 返回答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words1 = [\"amazon\",\"apple\",\"facebook\",\"google\",\"leetcode\"], words2 = [\"e\",\"o\"]\n",
    "<strong>输出：</strong>[\"facebook\",\"google\",\"leetcode\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words1 = [\"amazon\",\"apple\",\"facebook\",\"google\",\"leetcode\"], words2 = [\"l\",\"e\"]\n",
    "<strong>输出：</strong>[\"apple\",\"google\",\"leetcode\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words1 = [\"amazon\",\"apple\",\"facebook\",\"google\",\"leetcode\"], words2 = [\"e\",\"oo\"]\n",
    "<strong>输出：</strong>[\"facebook\",\"google\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words1 = [\"amazon\",\"apple\",\"facebook\",\"google\",\"leetcode\"], words2 = [\"lo\",\"eo\"]\n",
    "<strong>输出：</strong>[\"google\",\"leetcode\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words1 = [\"amazon\",\"apple\",\"facebook\",\"google\",\"leetcode\"], words2 = [\"ec\",\"oc\",\"ceo\"]\n",
    "<strong>输出：</strong>[\"facebook\",\"leetcode\"]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words1.length, words2.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= words1[i].length, words2[i].length &lt;= 10</code></li>\n",
    "\t<li><code>words1[i]</code> 和 <code>words2[i]</code> 仅由小写英文字母组成</li>\n",
    "\t<li><code>words1</code> 中的所有字符串 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [word-subsets](https://leetcode.cn/problems/word-subsets/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [word-subsets](https://leetcode.cn/problems/word-subsets/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"amazon\",\"apple\",\"facebook\",\"google\",\"leetcode\"]\\n[\"e\",\"o\"]', '[\"amazon\",\"apple\",\"facebook\",\"google\",\"leetcode\"]\\n[\"l\",\"e\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        res=[]\n",
    "        c2=Counter()\n",
    "        for i in words2:\n",
    "            c22=Counter(i)\n",
    "            for j in i:\n",
    "                c2[j]=max(c2[j],c22[j])\n",
    "        \n",
    "        for z in words1:\n",
    "            c11=Counter(z)\n",
    "            for t in c2:\n",
    "                if c2[t]>c11[t]:\n",
    "                    break\n",
    "            else:\n",
    "                res.append(z)\n",
    "        return res\n",
    "        \n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        c2=Counter()\n",
    "        res=[]\n",
    "        for wd in words2:\n",
    "            c22=Counter(wd)\n",
    "            for c in c22:\n",
    "                c2[c]=max(c2[c], c22[c])\n",
    "        # print(c2)\n",
    "        for wd in words1:\n",
    "            c11=Counter(wd)\n",
    "            for c in c2:\n",
    "                if c11[c]<c2[c]:\n",
    "                    break\n",
    "            else:\n",
    "                res.append(wd)\n",
    "        # print(count.__doc__)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        def count(word):\n",
    "            ans = [0] * 26\n",
    "            for letter in word:\n",
    "                ans[ord(letter) - ord('a')] += 1\n",
    "            return ans\n",
    "        \n",
    "        bmax = [0] * 26\n",
    "        for b in words2:\n",
    "            for i, c in enumerate(count(b)):\n",
    "                bmax[i] = max(bmax[i], c)\n",
    "\n",
    "        ans = []\n",
    "        for a in words1:\n",
    "            if all(x >= y for x, y in zip(count(a), bmax)):\n",
    "                ans.append(a)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        def count(word):\n",
    "            ans = [0] * 26\n",
    "            for c in word:\n",
    "                ans[ord(c) - ord('a')] += 1\n",
    "            return ans\n",
    "\n",
    "        bmax = [0] * 26\n",
    "        for b in words2:\n",
    "            for i, c in enumerate(count(b)):\n",
    "                bmax[i] = max(bmax[i], c)\n",
    "        res = []\n",
    "        for a in words1:\n",
    "            if all(x >= y for x, y in zip(count(a), bmax)):\n",
    "                res.append(a)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        from collections import defaultdict, Counter\n",
    "        max_count = defaultdict(int)\n",
    "        for word in words2:\n",
    "            count = defaultdict(int)\n",
    "            for ch in word:\n",
    "                count[ch] += 1\n",
    "            for ch in count:\n",
    "                max_count[ch] = max(max_count[ch], count[ch])\n",
    "\n",
    "        ans = []\n",
    "        for word in words1:\n",
    "            counter = Counter(word)\n",
    "            for ch in max_count:\n",
    "                if counter[ch] < max_count[ch]:\n",
    "                    break\n",
    "            else:\n",
    "                ans.append(word)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        def count(word):\n",
    "            res = [0] * 26\n",
    "            for ch in word:\n",
    "                res[ord(ch) - ord('a')] += 1\n",
    "            return res\n",
    "        words2cnt = [0] * 26\n",
    "        for word in words2:\n",
    "            wordcnt = count(word)\n",
    "            for i in range(len(wordcnt)):\n",
    "                words2cnt[i] = max(words2cnt[i], wordcnt[i])\n",
    "\n",
    "        res = []\n",
    "        for word in words1:\n",
    "            if all(x >= y for x, y in zip(count(word), words2cnt)):\n",
    "                res.append(word)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        c2=Counter()\n",
    "        res=[]\n",
    "        for wd in words2:\n",
    "            c22=Counter(wd)\n",
    "            for c in c22:\n",
    "                c2[c]=max(c2[c], c22[c])\n",
    "        # print(c2)\n",
    "        for wd in words1:\n",
    "            c11=Counter(wd)\n",
    "            for c in c2:\n",
    "                if c11[c]<c2[c]:\n",
    "                    break\n",
    "            else:\n",
    "                res.append(wd)\n",
    "        # print(count.__doc__)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        m = {}\n",
    "        for w2 in words2:\n",
    "            item = collections.defaultdict(int)\n",
    "            for c in w2:\n",
    "                item[c] += 1\n",
    "            for c, cnt in item.items():\n",
    "                m[c] = max(m.get(c, 0), cnt)\n",
    "        def isSub(word):\n",
    "            item = collections.defaultdict(int)\n",
    "            for c in word:\n",
    "                item[c] += 1\n",
    "            for c, cnt in m.items():\n",
    "                if item[c] < cnt:\n",
    "                    return False\n",
    "            return True\n",
    "        return [v for v in words1 if isSub(v)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, A: List[str], B: List[str]) -> List[str]:\n",
    "        B_char_freq = [0 for _ in range(26)]\n",
    "        for b in B:\n",
    "            tmp = self.func_count(b)\n",
    "            for i in range(26):\n",
    "                B_char_freq[i] = max(B_char_freq[i], tmp[i])\n",
    "        \n",
    "        res = []\n",
    "        for a in A:\n",
    "            tmp = self.func_count(a)\n",
    "            #if all (x >= y for x,y in zip(tmp, B_char_freq)):\n",
    "            if all (tmp[i] >= B_char_freq[i] for i in range(26)):\n",
    "                res.append(a)\n",
    "        return res\n",
    "    \n",
    "\n",
    "    def func_count(self, s: str) -> List[int]:\n",
    "        char_freq = [0 for _ in range(26)]\n",
    "        for c in s:\n",
    "            char_freq[ord(c) - ord('a')] += 1\n",
    "        return char_freq\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        def count(word):\n",
    "            res = [0] * 26\n",
    "            for letter in word:\n",
    "                res[ord(letter) - ord('a')] += 1\n",
    "            return res\n",
    "            \n",
    "        b = [0] * 26\n",
    "        for w in words2:\n",
    "            for i, c in enumerate(count(w)):\n",
    "                b[i] = max(b[i], c)\n",
    "        res = []\n",
    "        for a in words1:\n",
    "            if all(x >= y for x, y in zip(count(a), b)):\n",
    "                res.append(a)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#暴力\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        # words2内每个单词都在words1单词中，返回words1中的单词\n",
    "        # 组合[\"e\", \"o\"] -> [\"eo\"]\n",
    "        # 存dict, 如果word1[char]中出现次数>=words2[char]出现次数即可\n",
    "        #print(Counter(\"amazon\"))\n",
    "        return_dict = dict()\n",
    "        match_dict = Counter()\n",
    "        for i in words2:\n",
    "            c = Counter(i)\n",
    "            for k in c:\n",
    "                match_dict[k] = max(match_dict[k], c[k])\n",
    "\n",
    "        res = []\n",
    "        for i in range(len(words1)):\n",
    "            dic = Counter(words1[i])\n",
    "            add = True\n",
    "            for key in match_dict:\n",
    "                if match_dict[key] > dic[key] :\n",
    "                    add = False\n",
    "                    break\n",
    "            if add:\n",
    "                res.append(words1[i])\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        l = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        d = {}\n",
    "        for i in l:\n",
    "            d[i] = 0\n",
    "        for a in words2:\n",
    "            dic = {}\n",
    "            for i in a:\n",
    "                if i not in dic:\n",
    "                    dic[i] = 1\n",
    "                else:\n",
    "                    dic[i] += 1\n",
    "            key = list(dic.keys())\n",
    "            for i in key:\n",
    "                d[i] = max(d[i], dic[i])\n",
    "        # word2 = \"\"\n",
    "        # key = sorted(list(d.keys()))\n",
    "        # for i in key:\n",
    "        #     word2 += i*d[i]\n",
    "        dic = {}\n",
    "        for j in list(d.keys()):\n",
    "            if d[j] != 0:\n",
    "                dic[j] = d[j]\n",
    "        w = list(dic.keys())\n",
    "        ans = []\n",
    "        # print(dic)\n",
    "        # print(w)\n",
    "        for ii in words1:\n",
    "            ttmp = {}\n",
    "            for i in w:\n",
    "                ttmp[i] = 0\n",
    "            for j in ii:\n",
    "                if j not in w:\n",
    "                    continue\n",
    "                else:\n",
    "                    ttmp[j] += 1\n",
    "            # print(ttmp)\n",
    "            Flag = False\n",
    "            for i in w:\n",
    "                if dic[i] > ttmp[i]:\n",
    "                    Flag = True\n",
    "                    break\n",
    "            if Flag:\n",
    "                continue\n",
    "            ans.append(ii)\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        ret = []\n",
    "        cnt = Counter()\n",
    "        for w2 in words2:\n",
    "            cnt |= Counter(w2)\n",
    "        for w1 in words1:\n",
    "            cnt_w = Counter(w1)\n",
    "            if cnt_w & cnt == cnt:\n",
    "                ret.append(w1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        def count(word):\n",
    "            ans = [0] * 26\n",
    "            for letter in word:\n",
    "                ans[ord(letter) - ord('a')] += 1\n",
    "            return ans\n",
    "\n",
    "        bmax = [0] * 26\n",
    "        for b in words2:\n",
    "            for i, c in enumerate(count(b)):\n",
    "                bmax[i] = max(bmax[i], c)\n",
    "\n",
    "        ans = []\n",
    "        for a in words1:\n",
    "            if all(x >= y for x, y in zip(count(a), bmax)):\n",
    "                ans.append(a)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        value = [0] * 26\n",
    "        query_value = [0] * 26\n",
    "        key_value = [0] * 26\n",
    "        ans = []\n",
    "\n",
    "        for word in words2:\n",
    "            for c in word:\n",
    "                value[ord(c) - ord('a')] += 1\n",
    "                query_value[ord(c) - ord('a')] = max(query_value[ord(c) - ord('a')], value[ord(c) - ord('a')])\n",
    "            value = [0] * 26\n",
    "\n",
    "        for word in words1:\n",
    "            for c in word:\n",
    "                key_value[ord(c) - ord('a')] += 1\n",
    "            ans.append(word)\n",
    "            for j in range(26):\n",
    "                if key_value[j] < query_value[j]:\n",
    "                    ans.pop()\n",
    "                    break\n",
    "            key_value = [0] * 26\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        vis=defaultdict(int)\n",
    "        for word in words2:\n",
    "            temp=defaultdict(int)\n",
    "            for w in list(word):\n",
    "                temp[w]+=1\n",
    "            for k,v in temp.items():\n",
    "                if v>vis[k]:\n",
    "                    vis[k]=v\n",
    "        res=[]\n",
    "        for word in words1:\n",
    "            tar=Counter(list(word))\n",
    "            flag=1\n",
    "            for k,v in vis.items():\n",
    "                if v>tar[k]:\n",
    "                    flag=0\n",
    "                    break\n",
    "            if flag:\n",
    "                res.append(word)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        def count(s):\n",
    "            temp=[0]*26\n",
    "            for c in s:\n",
    "                temp[ord(c)-ord('a')]+=1\n",
    "            return temp\n",
    "        b=[0]*26\n",
    "        for sb in words2:\n",
    "            for i,k in enumerate(count(sb)):\n",
    "                b[i]=max(b[i],k)\n",
    "        ans=[]\n",
    "        for sa in words1:\n",
    "            if all(x>=y for x,y in zip(count(sa),b)):\n",
    "                ans.append(sa)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def wordSubsets(self, A, B):\n",
    "        def count(word):\n",
    "            ans = [0] * 26\n",
    "            for letter in word:\n",
    "                ans[ord(letter) - ord('a')] += 1\n",
    "            return ans\n",
    "\n",
    "        bmax = [0] * 26\n",
    "        for b in B:\n",
    "            for i, c in enumerate(count(b)):\n",
    "                bmax[i] = max(bmax[i], c)\n",
    "\n",
    "        ans = []\n",
    "        for a in A:\n",
    "            if all(x >= y for x, y in zip(count(a), bmax)):\n",
    "                ans.append(a)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        record = [0]*26\n",
    "        for word in words2:\n",
    "            temp = [0]*26\n",
    "            for ch in word:\n",
    "                temp[ord(ch)-ord('a')] += 1\n",
    "\n",
    "            for i in range(26):\n",
    "                record[i] = max(record[i], temp[i])\n",
    "\n",
    "        res = []\n",
    "        for word in words1:\n",
    "            record1 = [0]*26\n",
    "            for ch in word:\n",
    "                record1[ord(ch)-ord('a')] += 1\n",
    "\n",
    "            for i in range(26):\n",
    "                if record[i]>record1[i]:\n",
    "                    break\n",
    "            else:\n",
    "                res.append(word)\n",
    "\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        target = [0] * 27\n",
    "        res = []\n",
    "        for word in words2:\n",
    "            s = [0] * 27\n",
    "            for ch in word:\n",
    "                s[ord(ch) - ord('a')] += 1\n",
    "            for i in range(27):\n",
    "                target[i] = max(target[i], s[i])\n",
    "        for word in words1:\n",
    "            cnt = [0] * 27\n",
    "            for ch in word:\n",
    "                cnt[ord(ch) - ord('a')] += 1\n",
    "            i = 0\n",
    "            while i < 27:\n",
    "                if cnt[i] >= target[i]:\n",
    "                    i += 1\n",
    "                    continue\n",
    "                else:\n",
    "                    break\n",
    "            if i == 27:\n",
    "                res.append(word)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def wordSubsets(self, A, B):\n",
    "        def count(word):\n",
    "            ans = [0] * 26\n",
    "            for letter in word:\n",
    "                ans[ord(letter) - ord('a')] += 1\n",
    "            return ans\n",
    "\n",
    "        bmax = [0] * 26\n",
    "        for b in B:\n",
    "            for i, c in enumerate(count(b)):\n",
    "                bmax[i] = max(bmax[i], c)\n",
    "\n",
    "        ans = []\n",
    "        for a in A:\n",
    "            if all(x >= y for x, y in zip(count(a), bmax)):\n",
    "                ans.append(a)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        n2 = len(words2)\n",
    "        maxc = [0]*26\n",
    "        for word2 in words2:\n",
    "            tmp = [0]*26\n",
    "            for c in word2:\n",
    "                tmp[ord(c)-ord('a')] += 1\n",
    "                maxc[ord(c)-ord('a')] = max(maxc[ord(c)-ord('a')], tmp[ord(c)-ord('a')])\n",
    "        result = []\n",
    "        for word1 in words1:\n",
    "            tmp = [0]*26\n",
    "            for c in word1:\n",
    "                tmp[ord(c)-ord('a')] += 1\n",
    "            flag = True\n",
    "            for i in range(26):\n",
    "                if(tmp[i] < maxc[i]):\n",
    "                    flag = False\n",
    "                    break\n",
    "            if(flag):\n",
    "                result.append(word1)\n",
    "        return result\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def wordSubsets(self, A, B):\n",
    "        def count(word):\n",
    "            ans = [0] * 26\n",
    "            for letter in word:\n",
    "                ans[ord(letter) - ord('a')] += 1\n",
    "            return ans\n",
    "\n",
    "        bmax = [0] * 26\n",
    "        for b in B:\n",
    "            for i, c in enumerate(count(b)):\n",
    "                bmax[i] = max(bmax[i], c)\n",
    "\n",
    "        ans = []\n",
    "        for a in A:\n",
    "            if all(x >= y for x, y in zip(count(a), bmax)):\n",
    "                ans.append(a)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        target_dict = defaultdict(int)\n",
    "\n",
    "        for word in words2:\n",
    "            counts = Counter(word)\n",
    "            for letter in counts:\n",
    "                target_dict[letter] = max(target_dict[letter], counts[letter])\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        for word in words1:\n",
    "            counts = Counter(word)\n",
    "            for letter in target_dict:\n",
    "                if target_dict[letter] > counts[letter]:\n",
    "                    break\n",
    "            else:\n",
    "                ans.append(word)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\r\n",
    "        cnt = {}\r\n",
    "        _sum = 0\r\n",
    "        for word in words2:\r\n",
    "            _cnt = Counter(word)\r\n",
    "            for key, value in _cnt.items():\r\n",
    "                if key in cnt:\r\n",
    "                    cnt[key] = max(cnt[key], value)\r\n",
    "                else:\r\n",
    "                    cnt[key] = value\r\n",
    "\r\n",
    "        ans = []\r\n",
    "        for i, word in enumerate(words1):\r\n",
    "            tmp = cnt.copy()\r\n",
    "            for _c in word:\r\n",
    "                if _c in tmp:\r\n",
    "                    tmp[_c] -= 1\r\n",
    "                    if tmp[_c] == 0:\r\n",
    "                        del tmp[_c]\r\n",
    "                \r\n",
    "                if tmp == {}:\r\n",
    "                    ans.append(word)\r\n",
    "                    break\r\n",
    "        \r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        cnt = Counter()\n",
    "        for word in words2:\n",
    "            dct = Counter(word)\n",
    "            for w in dct:\n",
    "                cnt[w] = max(dct[w], cnt[w])\n",
    "        ans = []\n",
    "        for word in words1:\n",
    "            dct = Counter(word)\n",
    "            if all(dct[w] >= cnt[w] for w in cnt):\n",
    "                ans.append(word)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        w2 = collections.defaultdict(int)\n",
    "        for w in words2:\n",
    "            cnt=Counter(w)\n",
    "            for s in w:\n",
    "                w2[s] = max(w2[s], cnt[s])\n",
    "\n",
    "        ans = []\n",
    "        for k, w in enumerate(words1):\n",
    "            cnt=Counter(w)\n",
    "            for s in w2:\n",
    "                if cnt[s] < w2[s]:\n",
    "                    break\n",
    "            else:\n",
    "                ans.append(w)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        cnt = reduce(lambda x, y: x | y, (Counter(w) for w in words2))\n",
    "        return [w for w in words1 if Counter(w) >= cnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        l = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        d = {}\n",
    "        for i in l:\n",
    "            d[i] = 0\n",
    "        for a in words2:\n",
    "            dic = {}\n",
    "            for i in a:\n",
    "                if i not in dic:\n",
    "                    dic[i] = 1\n",
    "                else:\n",
    "                    dic[i] += 1\n",
    "            key = list(dic.keys())\n",
    "            for i in key:\n",
    "                d[i] = max(d[i], dic[i])\n",
    "        # word2 = \"\"\n",
    "        # key = sorted(list(d.keys()))\n",
    "        # for i in key:\n",
    "        #     word2 += i*d[i]\n",
    "        dic = {}\n",
    "        for j in list(d.keys()):\n",
    "            if d[j] != 0:\n",
    "                dic[j] = d[j]\n",
    "        w = list(dic.keys())\n",
    "        ans = []\n",
    "        # print(dic)\n",
    "        # print(w)\n",
    "        for ii in words1:\n",
    "            ttmp = {}\n",
    "            for i in w:\n",
    "                ttmp[i] = 0\n",
    "            for j in ii:\n",
    "                if j not in w:\n",
    "                    continue\n",
    "                else:\n",
    "                    ttmp[j] += 1\n",
    "            # print(ttmp)\n",
    "            Flag = False\n",
    "            for i in w:\n",
    "                if dic[i] > ttmp[i]:\n",
    "                    Flag = True\n",
    "                    break\n",
    "            if Flag:\n",
    "                continue\n",
    "            ans.append(ii)\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        def count(word):\n",
    "            ans = [0] * 26\n",
    "            for letter in word:\n",
    "                ans[ord(letter) - ord('a')] += 1\n",
    "            return ans\n",
    "        ans=[0]*26\n",
    "        for each in words2:\n",
    "            for i, c in enumerate(count(each)):\n",
    "                ans[i]=max(ans[i],c)\n",
    "        res=[]\n",
    "        for tmdnk in words1:\n",
    "            if all(x>=y for x,y in zip(count(tmdnk),ans)):\n",
    "                res.append(tmdnk)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        cnt = Counter()\n",
    "        for w in words2:\n",
    "            c = Counter(w)\n",
    "            for k,v in c.items():\n",
    "                cnt[k] = max(cnt[k], v)\n",
    "        ans = []\n",
    "        for w in words1:\n",
    "            c = Counter(w)\n",
    "            if all(c[k]>=cnt[k] for k in cnt.keys()):\n",
    "                ans.append(w)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        cnts = collections.defaultdict(int)\n",
    "        for word in words2:\n",
    "            tmp = collections.Counter(word)\n",
    "            for l in tmp:\n",
    "                if tmp[l] > cnts[l]: cnts[l] = tmp[l]\n",
    "        ans = []\n",
    "        for word in words1:\n",
    "            tmp, ok = collections.Counter(word), 1\n",
    "            for l in cnts:\n",
    "                if tmp[l] < cnts[l]:\n",
    "                    ok = 0\n",
    "                    break\n",
    "            if ok == 1: ans.append(word)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        c = Counter()\n",
    "        res = []\n",
    "        for each in words2:\n",
    "            word_counter = Counter(each)\n",
    "            for each_symbol in word_counter:\n",
    "                c[each_symbol] = max(c[each_symbol], word_counter[each_symbol])\n",
    "            # print(each)\n",
    "\n",
    "        for each in words1:\n",
    "            flag = 0\n",
    "            word1_counter = Counter(each)\n",
    "            # print(word1_counter)\n",
    "            for each_symbol in c:\n",
    "                # print(each_symbol)\n",
    "                if word1_counter[each_symbol] < c[each_symbol]:\n",
    "                    flag = 1   \n",
    "                    break\n",
    "            if flag == 0:\n",
    "                res.append(each)\n",
    "    \n",
    "        return res\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        def count_chars(word):\n",
    "            char_count = [0] * 26\n",
    "            for char in word:\n",
    "                char_count[ord(char) - ord('a')] += 1\n",
    "            return char_count\n",
    "        \n",
    "        target_char_count = [0] * 26\n",
    "        for word in words2:\n",
    "            word_char_count = count_chars(word)\n",
    "            for i in range(26):\n",
    "                target_char_count[i] = max(target_char_count[i], word_char_count[i])\n",
    "        \n",
    "        res = []\n",
    "        for word in words1:\n",
    "            word_char_count = count_chars(word)\n",
    "            if all(word_char_count[i] >= target_char_count[i] for i in range(26)):\n",
    "                res.append(word)\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        b = Counter()\n",
    "        for word in words2:\n",
    "            a = Counter(word)\n",
    "            for i in a.keys():\n",
    "                b[i] = max(a[i],b[i])\n",
    "        for word in words1:\n",
    "            c = Counter(word)\n",
    "            if all(c[i]>=b[i] for i in b.keys()):\n",
    "                ans.append(word)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        def count(word):\n",
    "            ans = [0] * 26\n",
    "            for letter in word:\n",
    "                ans[ord(letter) - ord('a')] += 1\n",
    "            return ans\n",
    "\n",
    "        bmax = [0] * 26\n",
    "        for b in words2:\n",
    "            for i, c in enumerate(count(b)):\n",
    "                bmax[i] = max(bmax[i], c)\n",
    "\n",
    "        for word in words1:\n",
    "            word_cnt = count(word)\n",
    "            for idx, bcnt in enumerate(bmax):\n",
    "                if word_cnt[idx] - bcnt >= 0:\n",
    "                    if idx == 25:\n",
    "                        res.append(word)\n",
    "                    continue\n",
    "                else:\n",
    "                    break\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "    \n",
    "    def merge_sub(self, subset):\n",
    "        word_dict = dict()\n",
    "        for subword in subset:\n",
    "            sub_dict = dict()\n",
    "            \n",
    "            for subchar in subword:\n",
    "                cnt = sub_dict.get(subchar, 0)\n",
    "                sub_dict[subchar] = cnt + 1\n",
    "            \n",
    "            for k,v in sub_dict.items():\n",
    "                res = word_dict.get(k,0)\n",
    "                word_dict[k] = max(res, v)\n",
    "\n",
    "        return word_dict\n",
    "\n",
    "    def isSubsets(self, subword_dict, word):\n",
    "        word_dict = dict()\n",
    "        for word_char in word:\n",
    "            cnt = word_dict.get(word_char, 0)\n",
    "            word_dict[word_char] = cnt + 1\n",
    "        \n",
    "        for k, v in subword_dict.items():\n",
    "            res = word_dict.get(k, 0)\n",
    "            if res<v:\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def wordSubsets(self, A, B):\n",
    "        def count(word):\n",
    "            ans = [0] * 26\n",
    "            for letter in word:\n",
    "                ans[ord(letter) - ord('a')] += 1\n",
    "            yield from ans\n",
    "\n",
    "        bmax = [0] * 26\n",
    "        for b in B:\n",
    "            for i, c in enumerate(count(b)):\n",
    "                bmax[i] = max(bmax[i], c)\n",
    "\n",
    "        ans = []\n",
    "        for a in A:\n",
    "            if all(x >= y for x, y in zip(count(a), bmax)):\n",
    "                ans.append(a)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        target = reduce(or_, map(Counter, words2))\n",
    "        return [w for w in words1 if Counter(w) >= target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        # words2_ana = [] \n",
    "        # for w in words2:\n",
    "        #     alpha_set = list(set(w))\n",
    "        #     alpha_and_count = {}\n",
    "        #     for a in alpha_set:\n",
    "        #         alpha_and_count[a] = list(w).count(a)\n",
    "        #     words2_ana.append(alpha_and_count)\n",
    "\n",
    "        \n",
    "        # result = []\n",
    "        # for word in words1:\n",
    "        #     ok = True\n",
    "        #     for check_dict in words2_ana:\n",
    "        #         for k,v in check_dict.items():\n",
    "        #             if list(word).count(k) < v:\n",
    "        #                 ok = False\n",
    "        #                 break\n",
    "        #     if ok:\n",
    "        #         result.append(word)\n",
    "        # return result\n",
    "        from collections import Counter        \n",
    "        cnt = [0] * 26\n",
    "        for word in words2:\n",
    "            for i in range(26):\n",
    "                cnt[i] = max(cnt[i], Counter(word)[chr(ord('a') + i)])\n",
    "        # 再依次比较\n",
    "        res = []\n",
    "        for word in words1:\n",
    "            flag = True\n",
    "            for i in range(26):\n",
    "                if cnt[i] > Counter(word)[chr(ord('a') + i)]:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                res.append(word)\n",
    "        return res\n",
    "        \n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        def count(word):\n",
    "            ans = [0] * 26\n",
    "            for letter in word:\n",
    "                ans[ord(letter) - ord('a')] += 1\n",
    "            return ans\n",
    "        b_max = [0] * 26\n",
    "        for word in words2:\n",
    "            for i, c in enumerate(count(word)):\n",
    "                b_max[i] = max(b_max[i], c)\n",
    "        ans = []\n",
    "        for word in words1:\n",
    "            if all(x >= y for x, y in zip(count(word), b_max)):\n",
    "                ans.append(word)\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        cnt = [0]*26\n",
    "        for b in words2:\n",
    "            for k,v in Counter(b).items():\n",
    "                cnt[ord(k)-ord('a')] =max(cnt[ord(k)-ord('a')],v)\n",
    "\n",
    "        ans = []\n",
    "        for w in words1:\n",
    "            find = True\n",
    "            cur = Counter(w)\n",
    "            for i in range(26):\n",
    "                k = chr(ord('a')+i)\n",
    "                if  cnt[i]!=0 and cnt[i]>cur[k]:\n",
    "                    find = False\n",
    "                    break\n",
    "            if find:\n",
    "                ans.append(w)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        ALPHABET = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        mask = {c: (1 << i) for i, c in enumerate(ALPHABET)}\n",
    "\n",
    "        def encode(t):\n",
    "            ans = 0\n",
    "            for c in t:\n",
    "                ans |= mask[c]\n",
    "            return ans\n",
    "\n",
    "        ss = Counter()\n",
    "        for t in words2:\n",
    "            cnt = Counter(t)\n",
    "            for k, v in cnt.items():\n",
    "                ss[k] = max(ss[k], v)\n",
    "        \n",
    "        ret = []\n",
    "        for t in words1:\n",
    "            cnt = Counter(t)\n",
    "            ok = True\n",
    "            for k, v in ss.items():\n",
    "                if cnt[k] < v:\n",
    "                    ok = False\n",
    "                    break\n",
    "            if ok:\n",
    "                ret.append(t)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def wordSubsets(self, A, B):\n",
    "        def count(word):\n",
    "            ans = [0] * 26\n",
    "            for letter in word:\n",
    "                ans[ord(letter) - ord('a')] += 1\n",
    "            return ans\n",
    "\n",
    "        bmax = [0] * 26\n",
    "        for b in B:\n",
    "            for i, c in enumerate(count(b)):\n",
    "                bmax[i] = max(bmax[i], c)\n",
    "\n",
    "        ans = []\n",
    "        for a in A:\n",
    "            if all(x >= y for x, y in zip(count(a), bmax)):\n",
    "                ans.append(a)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "class Solution:\r\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\r\n",
    "        pat=Counter()\r\n",
    "        for w in words2:\r\n",
    "            cnt=Counter(w)\r\n",
    "            for k,v in cnt.items():\r\n",
    "                pat[k]=max(pat[k],v)\r\n",
    "\r\n",
    "        ret=[]\r\n",
    "        for w in words1:\r\n",
    "            cnt=Counter(w)\r\n",
    "            for k,v in pat.items():\r\n",
    "                if cnt[k]<v:\r\n",
    "                    break\r\n",
    "            else:\r\n",
    "                ret.append(w)\r\n",
    "        return ret\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        d = {}\n",
    "        for word in words2:\n",
    "            d1 = collections.Counter(word)\n",
    "            for k, v in d1.items():\n",
    "                d[k] = max(v, d.get(k, 0))\n",
    "        \n",
    "        ans = []\n",
    "        for word in words1:\n",
    "            d1 = collections.Counter(word)\n",
    "            for k, v in d.items():\n",
    "                if v > d1.get(k, 0):\n",
    "                    break\n",
    "            else:\n",
    "                ans.append(word)\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        n=len(words1)\n",
    "        m=len(words2)\n",
    "        res=[]\n",
    "        def count(word):\n",
    "            ans = [0] * 26\n",
    "            for letter in word:\n",
    "                ans[ord(letter) - ord('a')] += 1\n",
    "            return ans\n",
    "        bmax = [0] * 26\n",
    "        for b in words2:\n",
    "            for i, c in enumerate(count(b)):\n",
    "                bmax[i] = max(bmax[i], c)\n",
    "\n",
    "        ans = []\n",
    "        for a in words1:\n",
    "            if all(x >= y for x, y in zip(count(a), bmax)):\n",
    "                ans.append(a)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        target = reduce(or_, map(Counter, words2))\n",
    "        return [w for w in words1 if Counter(w) >= target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        pattern = dict()\n",
    "        for word in words2:\n",
    "            curr = dict()\n",
    "            for i in word:\n",
    "                curr[i] = curr.get(i, 0) + 1\n",
    "            for i in curr:\n",
    "                pattern[i] = max(curr[i], pattern.get(i, 0))\n",
    "        \n",
    "        ans = []\n",
    "        for word in words1:\n",
    "            flag = True\n",
    "            curr = Counter(word)\n",
    "            for i in pattern:\n",
    "                if pattern[i] > curr[i]:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:    ans.append(word)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        def isSubset(a, b):\n",
    "            \"\"\"\n",
    "            判断 b 是否是 a 的子集\n",
    "            \"\"\"\n",
    "            for c in b:\n",
    "                if c not in a:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        \"\"\"\n",
    "        返回 words1 中所有的通用单词\n",
    "        \"\"\"\n",
    "        # 统计 words2 中每个字符出现的最大次数\n",
    "        max_count = [0] * 26\n",
    "        for word in words2:\n",
    "            count = [0] * 26\n",
    "            for c in word:\n",
    "                count[ord(c) - ord('a')] += 1\n",
    "            for i in range(26):\n",
    "                max_count[i] = max(max_count[i], count[i])\n",
    "        \n",
    "        # 遍历 words1，判断每个单词是否是通用单词\n",
    "        res = []\n",
    "        for word in words1:\n",
    "            count = [0] * 26\n",
    "            for c in word:\n",
    "                count[ord(c) - ord('a')] += 1\n",
    "            if all(count[i] >= max_count[i] for i in range(26)):\n",
    "                res.append(word)\n",
    "        \n",
    "        return res\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        table = Counter()\n",
    "        for w in words2:\n",
    "            ct = Counter(w)\n",
    "            for c in ct:\n",
    "                table[c] = max(table[c],ct[c])\n",
    "        ans = []\n",
    "        for w in words1:\n",
    "            cnt = Counter(w)\n",
    "            if all(c in cnt for c in table):\n",
    "                if all(cnt[c]>=table[c] for c in table):\n",
    "                    ans.append(w)\n",
    "        return ans\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        def count_chars(word):\n",
    "            char_count = [0] * 26\n",
    "            for char in word:\n",
    "                char_count[ord(char) - ord('a')] += 1\n",
    "            return char_count\n",
    "        \n",
    "        target_char_count = [0] * 26\n",
    "        for word in words2:\n",
    "            word_char_count = count_chars(word)\n",
    "            for i in range(26):\n",
    "                target_char_count[i] = max(target_char_count[i], word_char_count[i])\n",
    "        \n",
    "        res = []\n",
    "        for word in words1:\n",
    "            word_char_count = count_chars(word)\n",
    "            if all(word_char_count[i] >= target_char_count[i] for i in range(26)):\n",
    "                res.append(word)\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        c2=Counter()\n",
    "        res=[]\n",
    "        for wd in words2:\n",
    "            c22=Counter(wd)\n",
    "            for c in c22:\n",
    "                c2[c]=max(c2[c], c22[c])\n",
    "        # print(c2)\n",
    "        for wd in words1:\n",
    "            c11=Counter(wd)\n",
    "            for c in c2:\n",
    "                if c11[c]<c2[c]:\n",
    "                    break\n",
    "            else:\n",
    "                res.append(wd)\n",
    "        # print(count.__doc__)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        # def isSubset(a, b):\n",
    "        #     \"\"\"\n",
    "        #     判断 b 是否是 a 的子集\n",
    "        #     \"\"\"\n",
    "        #     for c in set(b):\n",
    "        #         if c not in set(a):\n",
    "        #             return False\n",
    "        #     return True\n",
    "\n",
    "        \"\"\"\n",
    "        返回 words1 中所有的通用单词\n",
    "        \"\"\"\n",
    "        # 统计 words2 中每个字符出现的最大次数\n",
    "        max_count = [0] * 26\n",
    "        for word in words2:\n",
    "            count = [0] * 26\n",
    "            for c in word:\n",
    "                count[ord(c) - ord('a')] += 1\n",
    "            for i in range(26):\n",
    "                max_count[i] = max(max_count[i], count[i])\n",
    "        \n",
    "        # 遍历 words1，判断每个单词是否是通用单词\n",
    "        res = []\n",
    "        for word in words1:\n",
    "            count = [0] * 26\n",
    "            for c in word:\n",
    "                count[ord(c) - ord('a')] += 1\n",
    "            if all(count[i] >= max_count[i] for i in range(26)):\n",
    "                res.append(word)\n",
    "        \n",
    "        return res\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        cnt = Counter()\n",
    "        for word in words2:\n",
    "            word_cnt = Counter(word)\n",
    "            for c in word:\n",
    "                cnt[c] = max(word_cnt[c], cnt[c])\n",
    "\n",
    "        ans = []\n",
    "        for word in words1:\n",
    "            word_cnt = Counter(word)\n",
    "            if all(word_cnt[c] >= cnt[c] for c in cnt):\n",
    "                ans.append(word)\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        pattern = dict()\n",
    "        for word in words2:\n",
    "            curr = dict()\n",
    "            for i in word:\n",
    "                curr[i] = curr.get(i, 0) + 1\n",
    "            for i in curr:\n",
    "                pattern[i] = max(curr[i], pattern.get(i, 0))\n",
    "        \n",
    "        ans = []\n",
    "        for word in words1:\n",
    "            flag = True\n",
    "            curr = Counter(word)\n",
    "            for i in pattern:\n",
    "                if pattern[i] > curr[i]:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:    ans.append(word)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        requiredChar = collections.defaultdict(int)\n",
    "        for word in words2:\n",
    "            tempMap = collections.defaultdict(int)\n",
    "            for c in word:\n",
    "                tempMap[c]+=1\n",
    "            for key in tempMap.keys():\n",
    "                if tempMap[key] > requiredChar[key]:\n",
    "                    requiredChar[key] = tempMap[key]\n",
    "        ret = []\n",
    "        for word in words1:\n",
    "            tempMap = collections.defaultdict(int)\n",
    "            for c in word:\n",
    "                tempMap[c]+=1\n",
    "            flag = False\n",
    "            for key in requiredChar.keys():\n",
    "                if tempMap[key] < requiredChar[key]: \n",
    "                    flag = True\n",
    "                    break\n",
    "            if not flag:\n",
    "                ret.append(word)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def wordSubsets(self, A, B):\n",
    "        def count(word):\n",
    "            ans = [0] * 26\n",
    "            for letter in word:\n",
    "                ans[ord(letter) - ord('a')] += 1\n",
    "            return ans\n",
    "\n",
    "        bmax = [0] * 26\n",
    "        for b in B:\n",
    "            for i, c in enumerate(count(b)):\n",
    "                bmax[i] = max(bmax[i], c)\n",
    "\n",
    "        ans = []\n",
    "        for a in A:\n",
    "            if all(x >= y for x, y in zip(count(a), bmax)):\n",
    "                ans.append(a)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "\n",
    "        def get_char_frequency(s):\n",
    "            freq = [0] * 26\n",
    "            for c in s:\n",
    "                freq[ord(c) - ord('a')]+=1\n",
    "            return freq\n",
    "        \n",
    "        max_freq = [0] * 26\n",
    "        res = []\n",
    "\n",
    "        for i in range(len(words2)):\n",
    "            cur = words2[i]\n",
    "            freq = get_char_frequency(cur)\n",
    "\n",
    "            for i in range(26):\n",
    "                max_freq[i] = max(max_freq[i], freq[i])\n",
    "        \n",
    "        for i in range(len(words1)):\n",
    "            cur = words1[i]\n",
    "            freq = get_char_frequency(cur)\n",
    "\n",
    "            for i in range(26):\n",
    "                if freq[i] < max_freq[i]:\n",
    "                    break\n",
    "                if i == 25:\n",
    "                    res.append(cur)\n",
    "        return res\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1, words2):\n",
    "        words2 = list(set(words2))\n",
    "        def jlzd(words):\n",
    "            # 建立字典\n",
    "            d = {}\n",
    "            for word in words:\n",
    "                for i in word:\n",
    "                    if i not in d:\n",
    "                        d[i] = word.count(i)\n",
    "                    else:\n",
    "                        if d[i] < word.count(i):\n",
    "                            d[i] = word.count(i)\n",
    "            return d\n",
    "        d = jlzd(words2)\n",
    "        ls = []\n",
    "        for i in words1:\n",
    "            bool = True\n",
    "            for j in d.keys():\n",
    "                if i.count(j) < d[j]:\n",
    "                    bool = False\n",
    "                    break\n",
    "            if bool:\n",
    "                ls.append(i)\n",
    "\n",
    "        return ls\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        ans, c0 = [], collections.Counter()\n",
    "        for w2 in [collections.Counter(i) for i in words2]:\n",
    "            for k in w2: c0[k] = max(c0[k], w2[k])\n",
    "        for w1 in words1:\n",
    "            c = collections.Counter(w1)\n",
    "            if all(c0[i]<=c[i] for i in c0): ans.append(w1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1, words2):\n",
    "        \"\"\"\n",
    "        \n",
    "        \n",
    "        \"\"\"\n",
    "        #处理异常情况\n",
    "        if words1 == None or words2 == None:\n",
    "            return []\n",
    "\n",
    "        words1_cnt = []\n",
    "\n",
    "        #使用字典保存字符串中的每个字符的各个字母的统计情况\n",
    "        for word in words1:\n",
    "            temp = [0 for _ in range(26)]\n",
    "            for c in word:\n",
    "                temp[ord(c) - ord('a')] += 1\n",
    "            words1_cnt.append(temp)\n",
    "\n",
    "        words2_cnt = [0 for _ in range(26)]        \n",
    "        #使用字典保存遍历words2之中各个子字符串的字母统计情况\n",
    "        for word in words2:\n",
    "            temp = [0 for _ in range(26)]\n",
    "            for c in word:\n",
    "                temp[ord(c) - ord('a')] += 1\n",
    "                if words2_cnt[ord(c) - ord('a')] < temp[ord(c) - ord('a')]:\n",
    "                    words2_cnt[ord(c) - ord('a')] = temp[ord(c) - ord('a')]\n",
    "           \n",
    "        ans = []\n",
    "        #再次遍历words1, 查看该字符是否都满足words2中的情况\n",
    "        for idx, word in enumerate(words1):\n",
    "            word_cnt = words1_cnt[idx]\n",
    "            flag = True \n",
    "            for i in range(26):\n",
    "                if words2_cnt[i] > word_cnt[i]:\n",
    "                    flag = False \n",
    "                    break \n",
    "\n",
    "            if flag:\n",
    "                ans.append(word)  \n",
    "\n",
    "        #return\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        dic = {}\n",
    "        for counter in [Counter(word) for word in words2]:\n",
    "            for k in counter:\n",
    "                if k not in dic or (k in dic and counter[k] > dic[k]):\n",
    "                    dic[k] = counter[k]\n",
    "\n",
    "        def check(word: str):\n",
    "            word_counter = Counter(word)\n",
    "            for k in dic:\n",
    "                if k not in word_counter or dic[k] > word_counter[k]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        result = []\n",
    "        for word in words1:\n",
    "            if check(word):\n",
    "                result.append(word)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        dic = {}\n",
    "        for counter in [Counter(word) for word in words2]:\n",
    "            for k in counter:\n",
    "                if k not in dic or (k in dic and counter[k] > dic[k]):\n",
    "                    dic[k] = counter[k]\n",
    "\n",
    "        def check(word: str):\n",
    "            word_counter = Counter(word)\n",
    "            for k in dic:\n",
    "                if k not in word_counter or dic[k] > word_counter[k]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        result = []\n",
    "        for word in words1:\n",
    "            if check(word):\n",
    "                result.append(word)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:\n",
    "        w2 = collections.Counter(words2[0])\n",
    "        for w in words2[1:]:\n",
    "            w2 += collections.Counter(w) - w2\n",
    "        # print(w2)\n",
    "        w1 = [collections.Counter(i) for i in words1]\n",
    "\n",
    "        ans = []\n",
    "        for k, v in enumerate(w1):\n",
    "            if w2 - v == collections.Counter():\n",
    "                ans.append(words1[k])\n",
    "\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
